package com.leetcode.LC;

import java.util.*;

public class LC448 {
    public List<Integer> findDisappearedNumbers(int[] nums) {//{1,2,2,3,3,4,7,8}

        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= nums.length; i++) {
            list.add(i);
        }

        for (int i = 0; i < nums.length-1; i++) {
            if (nums[i]!=nums[i+1]){
                for (int j = 0; j < list.size(); j++) {
                    if(list.get(j)==nums[i]){
                        list.remove(j);
                    }
                }
            }
        }
        for (int j = 0; j < list.size(); j++) {
            if(list.get(j)==nums[nums.length-1]){
                list.remove(j);
            }
        }
        return list;

    }

    public List<Integer> findDisappearedNumbers2(int[] nums) {//{1,2,2,3,3,4,7,8}

        Map<Integer, Boolean> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],true);
        }
        for (int i = 1; i <= nums.length; i++) {
            if (!map.containsKey(i)){
                list.add(i);
            }
        }
        return list;

    }

    public static void main(String[] args) {
        for (Integer disappearedNumber : new LC448().findDisappearedNumbers2(new int[]{4, 3, 2, 7, 8, 2, 3, 1})) {
            System.out.print(disappearedNumber + ",");
        }
    }
}
